package class27_recursionFormulaAndMatrix;

public class RecursionFormula {
    public static int[][] matrixMulti(int[][] a, int[][] b){
        /*
        *   矩阵乘法
        * */
        int[][] ans = new int[a.length][b[0].length];
        for(int i=0; i<a.length;i++){
            for(int j=0; j<b[0].length;j++){
                for(int k=0;k<a[0].length;k++){
                    ans[i][j] += a[i][k]*b[k][j];
                }
            }
        }
        return ans;
    }

    public static int[][] matrixPow(int[][] a, int p){
        /*
        * 矩阵幂次
        * 矩阵必须要是正方形
        * */
        int[][] ans = new int[a.length][a.length];
        for(int i=0;i<ans.length;i++){
            ans[i][i]=1;
        }
        while(p>0){
            if((p&1)!=0){
                ans = matrixMulti(ans,a);
            }
            a = matrixMulti(a,a);
            p=p >>> 1;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] a = {{1,1}};
        int[][] b = {{2,0},{0,2}};
        int[][] c = matrixPow(b,3);
        System.out.println(c);
    }
}
